package com.azzcs.v2.offer07;

import java.util.*;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 *
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *   3
 *  / \
 * 9  20
 *   /  \
 *  15  7
 * 示例 1:
 *
 *
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 * 示例 2:
 *
 * Input: preorder = [-1], inorder = [-1]
 * Output: [-1]
 *  
 *
 * 限制：
 *
 * 0 <= 节点个数 <= 5000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: azzcs
 * @Date: 2021/9/7 下午5:20
 */
public class Solution {
    private  Map<Integer, Integer> indexMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0){
            return null;
        }
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i],i);
        }
        return myBuildTree(preorder,0,preorder.length - 1,0,inorder.length-1);
    }

    public static void main(String[] args) {
//        int [] ints1 = new int[]{3, 9, 8, 5, 4, 10, 20, 15, 7};
//        int [] ints2 = new int[]{4, 5, 8, 10, 9, 3, 15, 20, 7};
        int [] ints1 = new int[]{1,2,3};
        int [] ints2 = new int[]{3,2,1};
        Solution solution = new Solution();
        TreeNode node = solution.buildTree(ints1, ints2);
        System.out.println(node);

    }

    private TreeNode myBuildTree(int[] preorder,  int pLeft, int pRight,int iLeft,int iRight) {
        if(pLeft > pRight){
            return null;
        }
        TreeNode node = new TreeNode(preorder[pLeft]);

        int index = indexMap.get(preorder[pLeft]);
        int leftNum = index - iLeft;
        node.left = myBuildTree(preorder,pLeft+1,pLeft + leftNum,iLeft,index-1);
        node.right = myBuildTree(preorder,pLeft + leftNum + 1,pRight,index +1,iRight);

        return node;
    }

    static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }
}
